On Concurrency Control By Multiple Versions

Reference

Christos H. Papadimitriou and Paris C. Kanellakis. 1982. On concurrency control by multiple versions. In Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS '82). ACM, New York, NY, USA, 76-82. DOI: https://doi.org/10.1145/588111.588125

論文の意義

Christos H. PapadimitriouによるMVCCにおけるトランザクションの定式化論文．

この論文でMVSRという概念が初出．従来のSerializabilityの幅を広げた．

Introduction

Concurrency Controlの責務はトランザクションのSerializabilityを保証すること．

保証したうえで，より並列性の高いアルゴリズムがベター．

これまでは1VCCしか存在しなかった．

さて，MVCCでは複数のVersionをストレージに保持することができる．となると，Read Operationにも選択肢が出来る．

どのVersionを読めばいいのか?いい，とはそもそも何か？を考えると，

これまでの，一つのKeyが一つのValueしか持たなかった1VCCとは，定式化も証明も異なってくる．

この論文では，1VCCにおけるSerializability(CSR)と異なる，MVSR(Multiversion Serializability)を提案している．

まず，口語的には，$ MVSR(s)は，以下とする:

あるread(x) は，それ以前に実行された write(x)の値を読むこととする．

ここは「それ以前」であり，「最新の値」でなくてもよい(Multiversionなので)

すべてのread(x)が，serial(直列/シングルスレッド)で実行されたときと同じwrite(x) の値を読む．

この制約が満たされるとき，$ MVSR(s)である．

「それ以前」を「最新」に変えたものが1VCCのSerializabilityであるから，$ CSR \subset MVSRといえる．

この論文は，MVSRのプロトコルや手法を紹介するわけではない．

この論文の目的は，「MVSRがいかに，どれだけ(計算が)難しいか」を説明することにある．

あるスケジュール$ sがMVSRであるかどうかを判定する問題がNP完全であることを示し，

また，巡回セールスマン問題のように，現実的に解くのが難しい組み合わせ問題であることを示し，

さらに，理論的にエレガントな枠組みがまだ用意できていないことを示す．

MVSRはlimit of the achivable parallelism，つまり「並列性の上界」を示すものであって，「実装上の上界」ではない．おそらく，もっと制約を加えないと実装は困難である．

# Introでここまで「出来てないこと」を言うのは慎ましい．．．

また，ここで現代では見聞きしない，ページモデル(The Page Model)以外の多くのモデルが紹介されている.

それについてはトランザクションのモデルにまとめる．

2. Multiversion Serializability

以下Definition/Notationの引用．

以下は基本．ページモデルと大体同じ．

$ T: トランザクション

$ T = (t_1, ..., t_m): トランザクションは$ tという要素からなる列

$ t_n: あるトランザクションにおける $ n個目の命令(step)．

$ R(\alpha), W(\alpha): Read/Write命令．つまり$ T = (R(x),W(y))のように表記できる.

$ E: データベースのエンティティの集合．$ R(\alpha)のとき$ \alpha \in E.

$ s: スケジュール．stepsからなる列．添字によってトランザクションを識別する．

e.g. $ s=R_1(a)R_1(b)R_2(b)R_1(c)W_1(c)W_3(b)R_3(a)R_3(c)W_3(c)W_2(b)

であるときのトランザクションはそれぞれ

$ T_1 = R(a)R(b)R(c)W(c)

$ T_2 = R(b)W(b)

$ T_3 = W(b)R(a)R(c)W(c)

$ serial\ schedule: トランザクションが一切interleaveしていないスケジュールのこと．

$ T_0: 初期化トランザクション．$ \{W_0(a): a \in E\}．全ての値を初期化している

$ T_f: 最終(final)トランザクション．$ \{R_f(a): a \in E\}．全ての値を最後に読んでいる

$ N(s): $ s \cup \{T_0, T_f\}.

$ T_0と$ T_fの扱いについては現代では議論が分かれるところ．後は順当．

Definition 1:

An interpretation $ I of s is a bipartite digraph $ I=(N(s),A), with nodes corresponding to the extended set of steps and arcs joining read and write steps only, where:

(a) each read step $ R_i(a) goes to exactly one write step $ W_j(a), with $ s(W_j(a))< s(R_i(a)).

(b) each write step goes to all previous read steps of the same transaction, and to no other steps.

stepをノードとする有向二部グラフ$ Iを描くことをinterpretationという．

以下の規則でエッジを張る．

(a) Readはprevious stepを読むという前提のもとで，いずれかのWriteに対してReadから張る．

(b) 同じトランザクション内で，readの後にwriteがあったなら，write -> readで張る．

この二部グラフ$ Iについて，$ R_f(a)のノードからエッジが張られているか，到達可能なノードをlive stepと呼ぶ．live stepからなる部分グラフをlive partと呼ぶ．

live partが一致する２つのスケジュールは等価(Equivalent)である，とする．

これはFinal State Serializability(FSR)．View Serializability(VSR)ではない．

1VCCにおけるinterpretation$ Iとは，各read stepが，スケジュール$ s上でlatestな，つまりその時点での最新の値を読む，というふうにエッジを張ったときのグラフである．

これはstandard interpretationと呼ぶ．

MVCCでは，各read stepが何を読むか，はアルゴリズムによって決定できるので，同じscheduleでも，得られるグラフは変わる．つまり，同じスケジュールでも異なるグラフになる.

Definition 2:

A schedule$ s is multi-version serializable (MVSR) if it has an interpretation equivalent to the standard interpretation of a serial schedule with the same transactions.

同じトランザクションからなる異なるスケジュール$ s, s'について，

一方$ sがserial scheduleであり，かつ$ sにstandard interpretationを行ったときのグラフ$ Gと，

同じグラフ$ G'を描ける$ s'のinterpretationが存在するならば，そのスケジュールはMVSR．

MVSRとこれまでのSerializabilityがFigure.3にまとめられている．

https://gyazo.com/c52fa0a6663b63615077714edbf49fbb

$ h_1の$ AはおそらくActionのこと?

standard interpretation以外も許されるという点で，MVSRが明らかに従来のSRを包含している．

The Complexitiy of MVSR

この章では，(あるスケジュールが)MVSR(であることを検証すること)がNP-Completeであることを証明する．

解説しながら引用．

Theorem 1: MVSR is NP-complete.

Proof:

That it is in NP is obvious, since an interpretation and a serial schedule can be guessed and checked in polynomial time.

あるスケジュールが与えられたとき，non-interleavedなserial scheduleを作るのと，それにstandard interpretationをかけて有向二部グラフを得る...のは多項式時間でできる．

よってMVSR性の検証がNPに属することは間違いない．

For NP-completeness, we reduce to MVSR the problem of testing whether a given polygraph is acyclic.

NP完全であることを証明するために，多項式時間で解ける問題に変形/還元する．

Polygraphが循環していないことを示す．

A polygraph [Pa1] is a triple P=(V,A,B),

where V is a finite set of vertices, AEVXV is a

set of arcs, and BE VX VX V is a set of bipaths.

In addition if bipath (u,v,w)EB we have

(w,u)EA. A &graph D=( V,A’) is said to be

compatible with P if A’ contains all of A, and

also, for each (u,u,w)EB, A’ also contains one

of (u,?J),(‘u,zu). A polygraph P is called acyclic

if there is an acyclic digraph compatible with

it. Testing whether a polygraph is acyclic is an

NP-complete problem Pal.

Given a polygraph P=( V,A,B), we shall construct

a schedule s (P) such that s (P)E MVSR

iff P is acyclic. The construction goes as follows:

For each vertex 21 E V, there is a transaction

T,, in s (P). The schedule itself is the concatenation

of several segments, corresponding

to the arcs and bipaths of P. (The precise order

of the concatenation does not matter, since all

steps in each of these segments read and

update a single entity, particular to the segment.)

For each arc a=(u,v)EA, we have the

segment R,(a)W,,(a). Finally, for each bipath

b=(u,v.w),

W,(b)R,(b).(sein.~~~~

the segment

We claim that P is acyclic iff s(P)EMVSR.

Suppose that P is acyclic. Then there is a

linear order of the nodes, say <, such that for

each (?I’ ,zr’)~A we have u’<v’ , and for each

(u,z~,w)@ we have either u<v, or v<zu. (To

see this, take < to be a topological ordering of

the dag which is compatible to P.) Obviously if

(u,v,w)~B then, because (w,u)~A and P is

acyclic, we have UJ <u. This total order, however,

corresponds to a serial schedule that is

equivalent to the following interpretation I of

s(P):

In I all read steps are assigned the last pretious

write step on the same entity, except for

the steps Rl(b), b=(u,v,W)EB, forwhichvcw.

To these steps I assigns W,(b). It is easy to

check that s(P), under I, is equivalent to the

serial schedule in which transaction T, executes

completely before T, iff u <v.

Conversely, if s (P)E MVSR, then it is rather

staightforward to show that the serial schedule

equivalent to some multiversion interpretation

of s(P) corresponds to a dag (in fact, a total

order) which is compatible with P. Q.E.D.